1. Field of the Invention
The present invention relates to an arithmetic decoding system. In particular, the present invention relates to an arithmetic decoding apparatus for decoding data encoded with context-adaptive binary arithmetic coding (CABAC).
2. Description of the Related Art
The context-adaptive binary arithmetic coding (CABAC) is a form of entropy coding used in H.264, which has been standardized by ITU-T (International Telecommunication Union—Telecommunication standardization sector) (see ITU-T H.264). In the CABAC, various types of non-binary data are converted to binary so as to be represented as symbols of “0” or “1” before encoding. Then, they are encoded by a binary arithmetic coding process. At the time of decoding, the inverse of the above process is performed.
The binary arithmetic coding process is a process of converting the data represented as the symbols of “0” or “1” from a {0, 1} form into an {LPS, MPS} form, where a most probable symbol (MPS) is one of the symbols “0” and “1” that is expected to occur the more likely and a least probable symbol (LPS) is the other of the symbols “0” and “1.” Then, the binary data, which is represented by two symbols of the LPS and the MPS, is encoded by arithmetic coding. Whether the MPS is “0” or “1” is determined by estimation for each symbol, based on already processed data. Specifically, at the time of encoding, the value of the MPS for a symbol that is to be encoded next is determined based on already encoded data alone, whereas at the time of decoding, the value of the MPS for a symbol that is to be decoded next is determined based on already decoded data alone.
In addition, in the binary arithmetic coding process, processing is performed while suitable probability models (contexts) are adopted one after another, from among a plurality of previously prepared probability models (contexts), depending on the current state. In the CABAC, context variables corresponding to the contexts are stored in a context variable table, and a context variable context[ctxIdx] is identified by a context index (ctxIdx). Each context variable is composed of a probability state index pStateIdx, which represents a probability of occurrence, and valMPS, which represents the most probable symbol (MPS), which is the more likely to occur. The probability state index pStateIdx represents an estimated value of the probability of the occurrence of the LPS in the current context, by one of previously defined probability states of 0 to 63. In addition, valMPS indicates whether the symbol that is the MPS is “0” or “1.” Note that, in each context variable, the probability state index is expressed as context[ctxIdx].pStateIdx, and the MPS is expressed as context[ctxIdx].valMPS.
FIG. 26 illustrates a concept of a decoding process in the CABAC. A decoder in the CABAC holds codIRange and codIOffset as internal state variables. In codIRange is stored a 9-bit value representing the width of a range that is assigned as a range corresponding to 100% probability of the occurrence of a next symbol. Therefore, a range that can be specified by codIRange is from 0 to 511. In codIOffset is stored a 9-bit value representing a code that is an object to be decoded. At the time of initialization, top 9 bits in a sequence of codes are read into codIOffset, whereas codIRange is set to 0x1FE (a number that follows “0x” represents a hexadecimal number. This is also true in the following descriptions).
Within codIRange, the width of a range assigned to an estimated probability of the occurrence of the MPS is codIRangeMPS, and the width of a range assigned to an estimated probability of the occurrence of the LPS is codIRangeLPS. Thus, if the value of codIOffset is equal to or greater than codIRangeMPS, a symbol of the LPS is decoded, whereas if the value of codIOffset is not equal to or greater than codIRangeMPS, a symbol of the MPS is decoded. With the value of 7th and 6th bits of codIRange, codIRange[7:6], as qCodIRangeIdx, codIRangeLPS is determined by referring to a table rangeTabLPS[pStateIdx][qCodIRangeIdx] as illustrated in FIG. 27. Meanwhile, codIRangeMPS is obtained by subtracting codIRangeLPS from codIRange.
As a result of decoding, valMPS is outputted as decoded data in the case of the MPS, whereas an inverse value of valMPS is outputted as the decoded data in the case of the LPS. Then, update of the internal state variables, codIRange and codIOffset, and update of the context variable context[ctxIdx] are performed. In the update of these values, processing varies depending on whether a decoding result is the MPS or the LPS.
(1) In the case where the decoding result is the MPS, pStateIdx transitions to transIdxMPS[context[ctxIdx].pStateIdx] in accordance with transIdxMPS in a transition table as illustrated in FIG. 28. Meanwhile, the value of valMPS remains context[ctxIdx].valMPS. The context variable context[ctxIdx] is updated so as to have these values. Meanwhile, codIOffset is not updated, whereas codIRange is updated to the value of codIRangeMPS.
(2) In the case where the decoding result is the LPS, pStateIdx transitions to transIdxLPS[context[ctxIdx].pStateIdx] in accordance with transIdxLPS in the transition table as illustrated in FIG. 28. At this time, the value of valMPS is changed to an inverse value of context[ctxIdx].valMPS if transIdxLPS[context[ctxIdx].pStateIdx] is “0,” whereas the value of valMPS remains the value of context[ctxIdx].valMPS if transIdxLPS[context[ctxIdx].pStateIdx] is not “0.” That is, if the LPS is decoded when pStateIdx=0, i.e., when the estimated value of the probability of the occurrence of the LPS is the greatest, it is determined that the symbol of the LPS has become the most probable, and accordingly the value of valMPS is inverted. Under any other condition, it is determined that the symbol of the MPS still remains the most probable, and accordingly the value of valMPS is not changed. The context variable context[ctxIdx] is updated so as to have these values. Moreover, the value of codIOffset is updated to the value of (codIOffset−codIRangeMPS), whereas the value of codIRange is updated to the value of codIRangeLPS.
The internal state variables are further subjected to updating and stream input in a renormalization process RenormD. In this renormalization process, codIRange is shifted to the left until codIRange becomes equal to or greater than 0x100 (=256). At the same time, codIOffset is shifted to the left by as many bits as codIRange is shifted to the left. At this time, one bit is inputted from a stream (encoded data) each time codIOffset is shifted to the left by one bit, whereby the 1-bit value of an LSB of codIOffset is updated. In this manner, the same number of bits are inputted from the input stream as the number of bits by which codIOffset is shifted to the left. In the case where codIRange is initially equal to or greater than 0x100, the internal state variables are not updated in the renormalization process. The above is a description of the decoding process for one symbol, and when each subsequent symbol is decoded, a similar process is repeated using ctxIdx newly calculated, so that the subsequent symbols are decoded one after another. Note that, hereinafter, the term “to shift” will be used to refer to “to shift to the left,” i.e., “to shift from the LSB side towards the MSB side.”
FIGS. 29 and 30 illustrate an exemplary circuit structure for a known binary arithmetic code decoding process in the CABAC as described above. FIGS. 31, 32, 33, and 34 illustrate procedures for the known binary arithmetic code decoding process in the CABAC.
When one symbol is decoded, pStateIdx and valMPS are read from the context variable table (step S901). The value of the 7th and 6th bits of the internal state variable codIRange is set in qCodIRangeIdx (step S902). Then, a reference value of rangeTabLPS[pStateIdx][qCodIRangeIdx] is set in codIRangeLPS, and a value obtained by subtracting codIRangeLPS from codIRange is set in codIRangeMPS (step S903).
At this time, if codIOffset is equal to or greater than codIRangeMPS (step S906), the decoding result is the LPS, and codIOffset is updated to a value obtained by subtracting codIRangeMPS from codIOffset, and codIRange is updated to the value of codIRangeLPS (step S907). In addition, the context variable is updated (step S910).
Meanwhile, if codIOffset is less than codIRangeMPS (step S906), the decoding result is the MPS, and codIRange is updated to the value of codIRangeMPS (step S908). In addition, the context variable is updated (step S920).
Thereafter, the internal state variables, codIRange and codIOffset, are subjected to the renormalization process (step S930).
In the case where the decoding result is the LPS (step S910), the inverse value of valMPS is outputted as decoded data (step S911). The next state of pStateIdx is derived from transIdxLPS[pStateIdx] in the transition table (step S912). At this time, if the value of transIdxLPS[pStateIdx] is “0” (step S913), the value of valMPS is inverted (step S914). Then, the context variable is updated so as to have the thus obtained values of pStateIdx and valMPS (step S915).
In the case where the decoding result is the MPS (step S920), the value of valMPS is outputted as decoded data (step S921). The next state of pStateIdx is derived from transIdxMPS[pStateIdx] in the transition table, and the context variable is updated so as to have the derived value of pStateIdx (step S922).
In the renormalization process (step S930), if codIRange is less than 0x0100 (=256) (step S931), both codIRange and codIOffset are shifted to the left bit by bit while one bit of the stream (the encoded data) is inputted into the LSB of codIOffset (step S932), until codIRange becomes equal to or greater than 0x0100.